package leetcode_161_180;

import java.util.*;

public class largestNumber_179 {
    public String largestNumber(int[] nums) {
        List<Integer>[] Nums=new List[9];   //按开头数字分类
        for(int i=0;i<9;i++)
            Nums[i]=new ArrayList<>();
        for (int num:nums)
            Nums[getStartNum(num)-1].add(num);
        StringBuilder result=new StringBuilder();
        for(int i=9;i>0;i--) {
            Nums[i - 1].sort(this::compare);  //用lamda自定义按字典序排序
            for (Integer num: Nums[i - 1])
                result.append(num.toString());
        }
         return result.toString();
    }
    /**
     * 比较两个数的从左开始，比较每一位
     * 返回更大者
     *无法解决
     343233432
     343234323
     且思路繁琐
     */
    public int compare(int a,int b){
        String s1 = Integer.toString(a);
        String s2 = Integer.toString(b);
        int minLength = Math.min(s1.length(), s2.length());

        // 逐位比较字符
        for (int i = 0; i < minLength; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 != c2) {
                 return c1 > c2 ? -1 : 1;     //默认升序是返回a - b , 我们需要降序，返回b-a，此时值为负数
            }
        }
        // 长度不同但前几位相同,  若较长的数字minLength+1 处大于 minlength 处 选择较长数字
        //如 34 和 3  选择 34 ，即返回-1，即选择   b - a 为负值
        if (s1.length() > s2.length()){
            return s1.charAt( minLength-1 ) < s1.charAt( minLength ) ? -1 : 1 ;
        } else if (s1.length() < s2.length()) {
            return s2.charAt( minLength-1 ) < s2.charAt( minLength ) ? 1 : -1 ;
        } else {
            return a; // 两个数字完全相等时返回任意值
        }
    }


    /**
     * 得到开头数字
     */
    public int getStartNum(int a){
        while(a/10 !=0)
            a/=10;
        return a;
    }


    /**
     * 修改了方法
     * @param nums
     * @return
     */
    public String largestNumber2(int[] nums) {
        int flag=0;
        for (int i:nums) {
            if(i!=0){
                flag=1;
                break;
            }
        }
        if(flag==0)return "0";
        //有可能出现数字0
        List<String>[] Nums=new List[10];   //按开头数字分类
        for(int i=0;i<10;i++)
            Nums[i]=new ArrayList<>();
        for (int num:nums)
            Nums[getStartNum(num)].add(Integer.toString(num));
        StringBuilder result=new StringBuilder();
        for(int i=9;i>-1;i--) {
            Nums[i].sort(this::compare2);  //用lamda自定义按字典序排序
            for (String num: Nums[i])
                result.append(num);
        }
        return result.toString();
    }

    public int compare2(String a,String b){
        return -(a+b).compareTo(b+a);
    }

    /**
     * 更简单，不用我想的那么麻烦
     * @param nums
     * @return
     */
    public String largestNumber3(int[] nums) {
        int flag=0;
        for (int i:nums) {
            if(i!=0){
                flag=1;
                break;
            }
        }
        if(flag==0) return "0";
        int n = nums.length;
        String[] ss = new String[n];
        for (int i = 0; i < n; i++) ss[i] = "" + nums[i];
        Arrays.sort(ss, (a, b) -> {
            String sa = a + b, sb = b + a ;
            return sb.compareTo(sa);
        });
        StringBuilder sb = new StringBuilder();
        for (String s : ss) sb.append(s);
        return sb.toString();
    }

    /**
     * 牛人手写快排代替排序器
     * @param nums
     * @return
     */
    public String largestNumber4(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
        if (nums[0] == 0) {
        return "0";
    }
    StringBuilder ans = new StringBuilder();
        for (int num : nums) {
        ans.append(num);
    }
        return ans.toString();
}

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = nums[start];
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            long x = 10;
            long y = 10;
            //数学拼接，大部分情况应该不会出现数字溢出
//            int x = 12; int y = 345
//            x 拼接 y = 12345 = 12 * 1000 + 345 = x * 1000 + y;
//            y 拼接 x = 34512 = 345 * 100 + 12 = y * 100 + x;

            while (nums[i] >= x) {
                x *= 10;
            }
            while (pivot >= y) {
                y *= 10;
            }
            //交换位置
            if (nums[i] * y + pivot > nums[i] + pivot * x) {
                index += 1;
                swap(nums, index, i);
            }
        }
        //递归快排
        swap(nums, index, start);
        quickSort(nums, start, index - 1);
        quickSort(nums, index + 1, end);
    }

    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}
